(a) Field of the Invention
The present invention relates to a method for iteratively decoding a block turbo code and a recording medium for storing an iterative decoding program of a block turbo code. More specifically, the present invention relates to a method for iteratively decoding a block turbo code and a recording medium for storing an iterative decoding program of a block turbo code, which are capable of reducing complexity and realizing iterative decoding without serious performance degradation when iterative decoding is performed using a soft decision output Viterbi decoding method for a product code obtained by serially concatenating systematic block codes.
(b) Description of the Related Art
An iterative decoding method using a soft decision output for a product code of a block code is referred to as a block turbo code. Contents related to the block turbo code are disclosed in U.S. Pat. No. 5,563,897.
According to the aforementioned patent, an algebraic decoding method is used in order to calculate the soft decision output. Such a decoding scheme has to refer to the decoder several times, so additional work is required to estimate the soft decision output.
A method for iteratively decoding block codes using a soft output Viterbi algorithm (SOVA) with a complexity-reduction technique is disclosed in Korean Patent Publication No. 2001-019469.
The operational principle of the decoding method of the above patent is as follows.
First, at an arbitrary r-th point of time of a trellis for an (n,k) block code, information on all paths is calculated and recorded.
Second, a surviving path is selected in each node.
Third, reliability, which is a metric difference value between the surviving path and a contending path is stored, that is, a soft decision output value is stored.
Fourth, the reliability values stored in a path from the point of time 0 to (r−1) are compared with the reliability value of the current contending path. The reliability value is updated according to the following rules.
When we denote the metric difference value between the surviving path and the contending path merging to the m-th state at the r-th point of time in the trellis as Δrm, an information bit calculated in the surviving path as ujs, and an information bit calculated in the contending path as ujc,If ujs≠ujc, Ljs=min(Ljs,Δrm), andIf ujs=ujc, Ljs=min(Ljs,Δrm+Ljc).
Fifth, the above work is repeated to the last point of time (an (n−1)-th point of time) of the trellis.
Sixth, the soft decision output for the decoded-word is the reliability value corresponding to the codeword, with polarity added.
A complexity-reducing technique is applied to the above SOVA according to the following principle.
There are a number of paths in the code trellis. Generally, the number of paths at a time point increases as the error correction capability of a code becomes greater. If the number of paths at a time point is comparatively large, the probability distribution of the path metric value follows the Gaussian distribution according to the central limit theorem.
This implies that we can easily know the A-th best path metric out of total S paths if we know the mean and the variance of the path metrics. This is because we know the probability distribution of the path metric follows the Gaussian distribution.
Therefore, the path metrics of the A paths are larger than a reference path metric (Pmri) at the i-th time point. Pmri may be obtained by Equation 1.
                              A                      S            i                          =                  {                                                                                                                ∫                                              P                                                  m                          ri                                                                    ∞                                        ⁢                                                                  1                                                                                                            2                              ⁢                              π                                                                                ⁢                                                      σ                            Pmi                                                                                              ⁢                                              exp                        ⁡                                                  (                                                      -                                                                                                                            (                                                                      x                                    -                                                                          m                                      Pmi                                                                                                        )                                                                2                                                                                            2                                ⁢                                                                  σ                                  Pmi                                  2                                                                                                                                              )                                                                    ⁢                                                                                          ⁢                                              ⅆ                        x                                                                              ⁢                                                                                                                                                                                  if                    ⁢                                                                                  ⁢                                          A                      /                                              S                        i                                                                              >                  0.5                                                                                                                          1                    -                                                                  ∫                                                  P                                                      m                            ri                                                                          ∞                                            ⁢                                                                        1                                                                                                                    2                                ⁢                                π                                                                                      ⁢                                                          σ                              Pmi                                                                                                      ⁢                                                  exp                          ⁡                                                      (                                                          -                                                                                                                                    (                                                                          x                                      -                                                                              m                                        Pmi                                                                                                              )                                                                    2                                                                                                  2                                  ⁢                                                                      σ                                    Pmi                                    2                                                                                                                                                        )                                                                          ⁢                                                                                                  ⁢                                                  ⅆ                          x                                                                                                      ⁢                                                                                                                                                                                  if                    ⁢                                                                                  ⁢                                          A                      /                                              S                        i                                                                              <                  0.5                                                                                        [                  EQUATION          ⁢                                          ⁢          1                ]            
wherein A is the number of paths to be sustained at each level (time point), Si is the number of total existing paths at the i-th level, mpmi is the mean of the path metrics at the i-th level, and σpmi is the standard deviation of the path metrics at the i-th level.
Therefore, the decoder calculates the reference path metric value Pmri and removes paths whose metric values are larger than Pmri in order to select the best A paths. In a real system, an integration value in Equation 1 may be tabled to thus be realized simply.
However, we may not estimate the reliability value in some cases if the above-mentioned method is applied to the SOVA. This kind of situation may occur due to the following reasons.
If the above complexity-reducing method is used, the decoder will eliminate some of the paths in order to keep only A paths out of S paths (S>A). Since some of the paths are eliminated, the decoder may confront nodes with only one incoming path rather than two, that is, the surviving and the contending paths. Accordingly, at such nodes, the surviving path will be determined automatically without comparing path metrics. We refer to these nodes as “Reliability non-definable; NR” nodes.
According to a basic principle of generating soft decision output information by the SOVA, a difference value between the surviving path and the contending path in an arbitrary node is defined as the soft decision output (or reliability value). When the contending path does not exist, it is impossible to define the soft decision output value.
In order to solve the above problem, we define the reliability at the NR nodes as the metric difference between the automatically determined surviving path and the reference path metric, Pmr.
FIG. 1 shows an example of a trellis diagram for a general (n, k) BCH code. As shown in the trellis diagram for a (7, 4) BCH code, the number of states in the trellis continuously increases from 0 to an (n-k−1)-th point of time. The number of states is sustained to be 2n-k from an (n-k−1)-th point of time to a (k−1)-th point of time. The number of states is continuously reduced from a (k−1)-th point of time to the (n−1)-th point of time.
When the systematic block code is assumed, in the trellis, a part from 0 to a (k−1)-th point of time corresponds to an information-word. A part from a k-th point of time to an (n−1)-th point of time corresponds to a parity-word.
In a parallel-concatenated block turbo code, it is not necessary to use reliability for parity-words. However, in a serially concatenated block turbo code using the product code, because the reliability value for parity-word parts also plays an important role, the reliability value must be calculated and used as an input for the next decoding.
When the complexity-reducing technique is applied in the parity-word part (the tail part) of the trellis, it may not be necessary to remove some paths because the number of paths is gradually reduced. Nevertheless, we may confront the NR codes due to the influences of the paths removed in the information-word part (the middle part) of the trellis.
In general, when the complexity-reducing technique is applied, the number of paths at an arbitrary point of time may be smaller than the number of paths to be sustained, that is A. Accordingly, a case where such path-removing work is not necessary may occur. Such a case mainly occurs in the parity-word part of the trellis.
In the above case of the tail part of the trellis, the value of the reference path metric is assigned as the smallest value among all of the existing paths in order to sustain all of the paths. Accordingly, the reliability value for the NR node in this case will be assigned as too optimistic a value because the reliability value is the difference between the path metric of the automatically generated surviving path and the reference path metric.
FIG. 2 shows distribution plots of the average of the reliability values in the information-word part and the parity-word part of the trellis with the number of iterations when the complexity-reducing technique is applied. The block turbo code using the product code of the (31, 20) expurgated BCH code is applied, and the maximum numbers of paths sustained by a decoder, A, are 256, 1024, and 2048.
FIG. 2A shows the distribution plot of the average of the reliability values in the information-word and parity-word parts when A is 256. FIG. 2B shows the distribution plot of the average of the reliability values in the information-word and parity-word parts when A is 1024. FIG. 2C shows the distribution plot of the average of the reliability values in the information-word and parity-word parts when A is 2048, which is the total number of existing paths, S.
Referring to FIG. 2, E(R) denotes the average of the reliability value, “Middle” denotes the information-word part of the trellis, and “Tail” denotes the parity-word part of the trellis. The total number of existing paths, S, is 2048.
When the total number of paths sustained by the decoder, A, is 2048, which is the same as the number of existing paths, S, as shown in FIG. 2C, the average of the reliability values of the information-word part of the trellis is almost equal to the average of the reliability value of the parity-word part of the trellis.
If A becomes far less than S, the difference between the average of the reliability value of the information-word part and the average of the reliability value of the parity-word part becomes larger. This implies that, in this case, the reliability value is evaluated to be far more optimistic in the parity-word part, that is, that the reliability values are assigned to be too large.
Therefore, the above decoding method efficiently operates for a parallel concatenated block turbo code where two block codes are concatenated to each other in parallel. When the two block codes are serially concatenated to each other, the complexity reduction technique with a certain amount of complexity reduction may cause serious performance degradation.